import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: AliceMana
 * Date: 2022-10-26
 * Time: 8:04
 */
public class Test {
    // https://leetcode.cn/problems/top-k-frequent-words/description/
    public List<String> topKFrequent(String[] words, int k) {
        // 将字符串中出现的单词及其次数储存在哈希表中
        Map<String, Integer> map = new HashMap<>();
        for (String s : words) {
            if (map.get(s) == null) {
                map.put(s, 1);
            } else {
                Integer val = map.get(s);
                map.put(s, val+1);
            }
        }
        // 此时已经将字符串数组中的所有单词储存在哈希表中了
        // 建立一个小根堆 传入一个比较器
        PriorityQueue<Map.Entry<String, Integer>> minHeap
                = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        // 遍历map中的每个元素， 将map中的前k个元素存入小根堆中
        // topK问题
        for (Map.Entry<String, Integer> m : map.entrySet()) {
            // 如果堆内元素个数小于k 直接offer
            if (minHeap.size() < k) {
                minHeap.offer(m);
            } else {
                // 将堆顶元素将m比较
                Map.Entry<String, Integer> top = minHeap.peek();
                // m的频率比堆顶元素大
                if (top.getValue().compareTo(m.getValue()) < 0) {
                    // 1. 将堆顶元素出堆
                    // 2. 将m放入堆
                    minHeap.poll();
                    minHeap.offer(m);
                } else {
                    // 频率相同
                    if (top.getValue().compareTo(m.getValue()) == 0) {
                        // 查看字典顺序
                        if (top.getKey().compareTo(m.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.offer(m);
                        }
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> top = minHeap.poll();
            ret.add(top.getKey());
        }
        // 小根堆， 翻转list
        Collections.reverse(ret);
        return ret;
    }



    // https://leetcode.cn/problems/contains-duplicate-ii/submissions/
    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        for (int i = 0; i < nums.length-1; i++) {
            for (int j = i+1; j <= i + k && j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,1,2,3};
        System.out.println(containsNearbyDuplicate(arr, 2));
    }
}
